import java.util.HashMap;
import java.util.Map;

/**
 * 斐波那契数列,现要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项为1)
 */

public class suanfa08 {
    public int Fibonacci1(int n) {
        if (n == 0) {
            return n;
        }
        int first = 1;
        int second = 1;
        int third = 1;
        while (n > 2) {
            third = first + second;
            first = second;
            second = third;
            n--;
        }
        return third;
    }
    //分治法 , 将大问题化解为小问题
    private Map<Integer,Integer> filter = new HashMap<>();
    public int Fibonacci2(int n) {
        if (n == 0 || n == 1) {
            return  n;
        }
        int pre = 0;
        if (filter.containsKey(n-1)) {
            pre = filter.get(n-1);
        }else {
            pre = Fibonacci2(n-1);
            filter.put(n-1,pre);
        }
        int ppre = 0;
        if (filter.containsKey(n-2)) {
            ppre = filter.get(n-2);
        }else {
            ppre = Fibonacci1(n-2);
            filter.put(n-2,ppre);
        }
        return pre + ppre;
    }
}
